// https://www.lintcode.com/problem/maximum-subarray-ii/

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(List<Integer> nums) {
        // write your code here
        int nlen = nums.size();
        int[] max_from_left = new int[nlen]; // 从左边开始到当前位置的连续最大和
        int[] max_from_right = new int[nlen]; // 从右边开始到当前位置的连续最大和
        Arrays.fill(max_from_left, 0);
        Arrays.fill(max_from_right, 0);
        int sum = 0;
        int min = 0; // 比0小的要扣除！！！
        int max = nums.get(0);
        for (int i = 0; i < nlen; ++i) { // 从左到右
            sum += nums.get(i);
            max = Math.max(max, sum - min);
            min = Math.min(min, sum);
            max_from_left[i] = max;
        }
        sum = 0;
        min = 0;
        max = nums.get(nlen - 1);
        for (int i = nlen - 1; i >= 0; --i) {
            sum += nums.get(i);
            max = Math.max(max, sum - min);
            min = Math.min(min, sum);
            max_from_right[i] = max;
        }
        max = max_from_left[0] + max_from_right[nlen - 1];
        for (int i = 0; i < (nlen - 1); ++i) {
            max = Math.max(max, max_from_left[i] + max_from_right[i + 1]);
        }
        return max;
    }
}